Image descriptors are used for a variety of tasks in graphics and computer vision where matching one image to another is desired. For example, image descriptors are often used for 3D reconstruction tasks, and as a first stage in object or place recognition. Image descriptors are also used for searching databases of photographs. For instance, a query image, such as one captured by a cell phone camera, can be matched into a database containing thousands or millions of images of locations in a city. Rather than storing images, descriptors which characterize each image are stored. This allows a quick and efficient search process to match descriptors extracted from the query image to those in the database. An image descriptor is a vector of numbers which are ideally invariant to common image transformations and can be compared with other descriptors in a database to obtain matches according to a distance metric.